<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>

<script>
    //双向链表的封装
    function DBLinkedList(){
        //the node of the list
        function Node(data){
            this.data = data;
            this.next = null;
            this.prev = null;
        }
        //property
        this.head = null;
        this.tail = null;
        this.length = 0;

        //method
        DBLinkedList.prototype.append = function(data){
            var newNode = new Node(data);

            var current = this.head;
            if(this.length === 0){
                this.head = newNode;

            }else{
                while(current.next){
                    current = current.next;
                }
                current.next = newNode;
                newNode.prev = current;
            }
            //可以写成this.length+=1;有些语言中不支持++ ；比如Python
            this.length ++ ;
            this.tail = newNode;

        };

        //2.0将链表转化为字符串的形式
        //2.1toString方法
        DBLinkedList.prototype.toString = function(){
            return this.backwardString();
        };
        //2.2 forwardString 方法
        //从后向前遍历
        DBLinkedList.prototype.forwardString = function(){
            var current = this.tail,
                resultString = "";
            while(current){
                resultString += current.data +" ";
                current = current.prev;
            }

            return resultString;
        };

        //2.3 backwardString方法 向后遍历
        DBLinkedList.prototype.backwardString = function(){
            var current = this.head,
                resultString = "";
            while (current) {
                resultString += current.data +" ";
                current = current.next;
            }


            return resultString;
        };

        //3、插入元素
        //3.1、insert 在链表特定位置插入一个新的元素
        DBLinkedList.prototype.insert = function(position,data){
            //position越界检测
            if(position<0||position>this.length){
                return false;
            }
            var newNode = new Node(data);
            //遍历到position处并添加元素
            var index = 0,
                current = this.head;

            if(position === 0){
                newNode.next =this.head;
                this.head.prev = newNode
                this.head = newNode;
            }else{
                //要考虑在最末尾添加元素的情况
                while(index<position-1){
                    index++;
                    current = current.next;
                }
                if(current.next){
                    newNode.prev = current;
                    newNode.next = current.next;
                    current.next.prev = newNode;
                    current.next = newNode;
                }else{
                    current.next = newNode;
                    newNode.prev = current;
                    this.tail = newNode;
                }



            }

            //length++
            length++;
            return true;

        };

        //4.0 查找元素
        //4.1 get(position) 获取队以哦那个位置的元素
        DBLinkedList.prototype.get = function (position){
            //position 越界检测
            if(position<0||position>=this.length){
                return -1;
            }
            //遍历到position处
            var current = this.head,
                index = 0;

            while(index<position){
                index++;
                current = current.next;
            }

            //返回
            return current.data;
        };

        //4.2 获取数据在链表中的索引
        DBLinkedList.prototype.indexOf = function(data){
            var index = 0,
                current = this.head;
            //遍历查找data相等的元素
            var result = -1;
            //循环语句中如果涉及到对循环条件的操作，放到最后执行。否则在第一次执行的时候会出错
            while(current.next){
                if(current.data === data){
                    result = index;
                    break;
                }
                index ++;
                current = current.next;
                //即使使用=== 也无法完成类型匹配
            }
            //如果没有找到 返回值
            return result;
            //返回
        };

        //4.3 获取第一个元素
        DBLinkedList.prototype.getHead = function(){
            return this.head;
        };
        //4.4 获取最后一个元素
        DBLinkedList.prototype.getTail = function(){
            return this.tail;
        };

        //5、修改
        //5.1 update（position,element） 修改某个地方的值
        //=====================可以更新
        DBLinkedList.prototype.update = function(position,data){
          //postion 越界判断
          if(position <0||position>=this.length){
              return false;
          }
          // 找到position处
            var current = this.head;
          var index  = 0;
          while(index<position){
              index++;
              current = current.next;
          }
          current.data = data;

          //优化：判断position的大小与this.lenght一半之间的大小关系，以决定是从前往后遍历还是从后向前遍历。


        };

        //6、删除
        //6.1 removeAt()
        DBLinkedList.prototype.removeAt = function(position){
            //position 越界判断
            if(position<0||position>=this.length){return null}
            //链表中只存在一个节点
            if(this.length == 1){
                this.head = null;
                this.tail = null;
            }else{
                var current = this.head;
                var index = 0;
                //删除第一个，需要改变this.head指向
                if(position==0){
                    current = this.head;
                    this.head.next.prev = null;
                    this.head = this.head.next;


                }else if(position==this.length-1){
                    //删除最后一个
                        current = this.tail;
                        this.tail = this.tail.prev;
                        this.tail.next = null;

                }else{
                    //删除中间

                    while(index<position){
                        index++;
                        current = current.next;
                    }
                    current.prev.next =  current.next;
                    current.next.prev = current.prev;


                }
                this.lenght--;
                return current.data;



            }


        };

        //6.2 remove(data)
        DBLinkedList.prototype.remove = function(data){
            var index = this.indexOf(data);
            return this.removeAt(index);
        };

        // 7、常规
        //7.1 isEmpty
        DBLinkedList.prototype.isEmpty = function(){
            return this.length === 0;
        };

        //7.2
        DBLinkedList.prototype.size = function(){
            return this.length;
        };






    }

    //测试
    var list = new DBLinkedList();

    list.append("123");
    list.append("456");
    list.append("asdf");
    list.append("fd");
    list.append("wqs");
    list.append({data:"1",game:"马里奥"});

    console.log(list);
    console.log(list.backwardString());
    console.log(list.toString());
    console.log(list.forwardString());
    //list.insert(this.length,) 中this指向？？
    console.log(list.insert(list.length, "cdt"));
    console.log(list.toString());
    // console.log(list.get(list.length));

    console.log(list.indexOf("456"));
    console.log(list.tail);
    list.update(0,"111");
    console.log(list.toString());
    console.log(list.removeAt(0));
    console.log(list.toString());
    // console.log(list.remove("asdf"));
    // console.log(list.toString());
    console.log(list.size());
    console.log(list.isEmpty());
    console.log(list.getHead());
    console.log(list.getTail());

</script>
</body>
</html>